package everyday;

/**
 * @author zhangmin
 * @create 2022-04-25 9:45
 * 实现strStr()函数。
 * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回-1 。
 * 思路
 * KMP算法，匹配needle时当匹配到某一位不一致了，则不需要全部退回头去比较，而是退回到最长前缀位置，这个退回的位置用next数组记录，next只和needle有关
 * 和haystack无关
 */
public class strStr28 {
    public int strStr(String haystack, String needle) {
        int hn=haystack.length(),nn=needle.length();
        haystack=" "+haystack;
        needle=" "+needle;
        char[] hc = haystack.toCharArray();
        char[] nc = needle.toCharArray();
        int[] next=new int[nn+1];
        //构造next数组，从i=2开始
        for (int i = 2,j=0; i <= nn; i++) {
            while (j>0&&nc[i]!=nc[j+1]) j=next[j];
            if (nc[i]==nc[j+1]) j++;
            next[i]=j;
        }
        //匹配阶段，从i=1开始
        for (int i = 1,j=0; i <= hn; i++) {
            while (j>0&&hc[i]!=nc[j+1]) j=next[j];
            if (hc[i]==nc[j+1]) j++;
            if (j==nn){
                return i-nn;
            }
        }
        return -1;
    }
}
